1. Field of the Invention
This invention relates to the field of computing devices, and in particular to the field of binary multiplication.
2. Description of Related Art
The representation of negative numbers in a binary number system can take a variety of forms. Two common representations are sign-magnitude (SM), and twos complement (2""s). In the sign-magnitude representation, a sign-bit is used to represent the algebraic sign of the number, and an independent set of bits are used to represent the magnitude of the number. In the twos complement representation, negative numbers are represented as the result of a subtraction of the magnitude of the number from zero. That is, in a four bit system, for example, a negative 2 is represented as the result of 0000 minus 0010, which is 1110 (the borrow, or carry, produced by the subtraction is ignored). The twos complement representation has the advantageous characteristic that additions and subtractions of twos complement numbers can be effected without regard for whether the numbers being added or subtracted are positive or negative. That is, the addition of 5 (0101) to a negative 2 (1110) is 3 (0011) (the borrow, or carry, produced by the addition is ignored). The sign-magnitude representation requires a specific consideration of the sign bit of each number to determine whether, for example, an xe2x80x9cadditionxe2x80x9d is actually a subtraction of magnitudes depending upon the sign of each number being added. That is, the addition of 5 (+0101) to a negative 2 (xe2x88x920010) is effected by subtracting 2 (0010) from 5 (0101) to produce a magnitude of 3 (0011). The sign of the result also requires a comparison of the magnitudes of each number as well.
The sign-magnitude representation, on the other hand, is well suited for multiplication, while the twos complement representation cannot be used directly to perform multiplication. FIG. 1 illustrates the problem. Shown in FIG. 1 is the binary multiplication of the binary numbers 1010 and 0111 to produce the binary product 01000110. As is common in the art, the multiplication of two numbers is often performed as a sequence of sub-multiple multiplications, so as to allow the use of a smaller, less costly, multiplier. In general, an Nxc3x97M bit multiplication is effected by a sequence of N/jxc3x97M/k bit multiplications, where N, M, j, k, N/j, and M/k are integers. That is, for example, the multiplication of two 32 bit numbers can be preformed as a sequence of repeated 16 bit multiplications (N/2xc3x97M/2), or a sequence of 16 bit by 8 bit multiplications (N/2xc3x97M/4), and so on. The results of each sub-multiplication are accumulated, appropriately shifted dependent upon the place of the submultiples, to form the product. FIG. 1 illustrates the multiplication of the two four-bit numbers (4xc3x974 bit multiplication) as a sequence of two-bit submultiple multiplications (4/2xc3x974/2 bit multiplications). The submultiples of the two number N1, N2 being multiplied are identified as H1, L1, and H2, L2 respectively. The H and L notations are used to signify high-order and low-order submultiples, respectively. In binary form, the value of the binary submultiple L1 is 11, and the value of the binary submultiple L2 is 10. The product of L1 and L2 is identified as L1*L2 in FIG. 1, and has the value 0110. In decimal magnitude form, the value of L1 (11) is 3, the value of L2 (10) is 2, and the product of L1 and L2 (0110) is 6. In like manner, the product of submultiples L1 (11) and H2 (10) is identified as L1*H2 in FIG. 1, and has the value of (0110) shifted left two places (011000), corresponding to the place of H2 being two places to the left.
The product of submultiples H1 (01) and L2 (10) is identified as H1*L2 in FIG. 1, and has the value of (0010) shifted left two places (001000), corresponding to the place of H1 being two places to the left. The product of submultiples H1 (01) and H2 (10) is identified as H1*H2 in FIG. 1, and has the value of (0010) shifted left four places (00100000), corresponding to the place of H1 and H2 each being two places to the left.
In decimal magnitude form, the value of subproducts L1*L2 (0110), L1*H2 (011000), H1*L2 (001000), and H1*H2 (00100000) are 6, 24, 8, and 32, respectively. The sum of these binary subproducts is 01000110, which in decimal form is 70, the product of the numbers N1 (7) and N2 (10). That is, if the binary numbers 0111 and 1010 represent decimal magnitudes 7 and 10, the sum of the products of their submultiples accurately represents their product as a decimal magnitude, 70.
In twos complement form, however, the binary numbers 0111 and 1010 represent decimal values 7 and xe2x88x926, respectively. The binary product of these two binary numbers, 01000110, does not, however, accurately represent their product, xe2x88x9242.
Conventionally, the multiplication of twos complement numbers is effected by first converting the twos complement numbers into sign-magnitude form, and multiplying the magnitudes. If the signs of the multiplicands differ, the product of the magnitudes is converted to a negative number in twos complement form. FIG. 2 illustrates this process, using the same multiplicands as in FIG. 1. The twos complement representation (1010) of xe2x88x926 is converted to a negative sign S1, and a magnitude of 6 (0110 ). The twos complement representation (0111) of 7 is converted to a positive sign S2, and a magnitude of 7 (0111). The binary product of 0111 (7) and 0110 (6) is 01000110 (42). Because the sign S1, S2 of the multiplicands differ, the product 01000110 (42) is converted to the negative of 01000110 in twos complement form 11010110, thereby producing the proper result, xe2x88x9242 in twos complement form.
Note that the twos complement conversion is applied to the original four-bit wide number, and thereafter the multiplication is effected on the narrower two-bit wide submultiples. As noted above, narrower operations consume less area of circuitry, and therefore are less costly, than wider operations (the terms wide and narrow are used herein to describe the number of bits comprising a number, independent of the magnitude of the number, a wide number having more bits than a narrow number). The conversions of a wide number between twos complement form and sign-magnitude form is time consuming, and the circuitry required to effect the conversions is area consuming. Therefore, a need exists for a device or process that allows for the multiplication of twos complement numbers that does not require a wide twos complement conversion.
It is an object of this invention to provide a process and device that allows for the multiplication of twos complement numbers without a wide conversion to and from twos complement form. This object and others are achieved by partitioning the operands of an Nxc3x97M bit multiplication into N/j+1 bit and M/k+1 bit submultiples, respectively. The most significant submultiple is assigned the sign of the operand, while each of the less significant submultiple is assigned a positive sign. The product of each submultiple pair is sign extended to the width of the product (N+M), and the accumulation of these sign extended submultiple products provides the product of the original twos complement operands, in twos complement form.